BIT Algo/2. Zajęcia/Zadanie 2. (sortowanie tablicy stringów w czasie liniowym).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Mamy daną tablicę stringów, gdzie suma długości wszystkich stringów daje $ n $. Napisz algorytm, który posortuje tablicę w czasie $ O(n) $. Można założyć, że stringi składają się wyłącznie z małych liter afabetu łacińskiego."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ nie mamy nic powiedzianego, że rozkład stringów o tej samej sługości lub stringów, które się rozpoczynają tą samą literą, jest jednostajny, więc nie możmy wykorzystać Bucket Sorta. Podobnie Counting Sort się również nie nada, ponieważ za bardzo nie da się zliczać całych stringów i ich zapisywać pod odpowiednim indeksem w tablicy. W tej sytuacji najlepiej sprawdzi się Radix Sort, który posortuje stringi według kolejnych znaków. Ponieważ interesuje nas porządek leksykograficzny, sortowanie musimy rozpocząć od najmniej znaczącego znaku (litery), czyli od prawej strony najdłuższego z wyrazów. Do posortowania stringów według wskazanego znaku (indeksu kolumny) wykorzystamy (jako algorytm pomocniczy) Counting Sorta."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Istnieje 26 małych liter alfabetu łacińskiego, dlatego takiego rozmiaru tablicę $ counts $ tworzymy w Counting Sorcie."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def radix_string_sort(arr):\n",
    "    # Sort strings by lengths (to improve the efficiency of\n",
    "    # sorting strings by letters)\n",
    "    max_len = longest_string_length(arr)\n",
    "    _counting_sort_by_length(arr, max_len)\n",
    "    # Allocate a temporary array once before sorting\n",
    "    temp = [None] * len(arr)\n",
    "    # Sort in a loop by the least significant digit\n",
    "    for col_idx in range(max_len-1, -1, -1):\n",
    "        _counting_sort(arr, col_idx, temp)\n",
    "        \n",
    "\n",
    "def _counting_sort_by_length(arr, max_len):\n",
    "    # Allocate memory for required temporary arrays\n",
    "    counts = [0] * (max_len + 1)\n",
    "    temp = [None] * len(arr)\n",
    "    # Count strings with the same lengths\n",
    "    for string in arr:\n",
    "        counts[len(string)] += 1\n",
    "    # Modify the counts array to indicate how many strings \n",
    "    # are of a length not greater than the current string's length\n",
    "    for i in range(1, len(counts)):\n",
    "        counts[i] += counts[i-1]\n",
    "    # Rewrite values to the temp sorted array\n",
    "    for i in range(len(arr)-1, -1, -1):\n",
    "        counts[len(arr[i])] -= 1\n",
    "        temp[counts[len(arr[i])]] = arr[i]\n",
    "    # Rewrite sorted values to the initial array\n",
    "    for i in range(len(temp)):\n",
    "        arr[i] = temp[i]\n",
    "\n",
    "        \n",
    "def _counting_sort(arr, col_idx, temp):\n",
    "    # Allocate memory for required temporary arrays\n",
    "    counts = [0] * 26\n",
    "    a_code = ord('a')\n",
    "    # Count letters repetitions\n",
    "    i = len(arr)-1\n",
    "    while col_idx < len(arr[i]) and i >= 0:\n",
    "        counts[ord(arr[i][col_idx]) - a_code] += 1\n",
    "        i -= 1\n",
    "    prev_to_last_idx = i\n",
    "    # Modify the counts array to indicate how many letters have\n",
    "    # ascii codes lower than or equal to the current one\n",
    "    for i in range(1, len(counts)):\n",
    "        counts[i] += counts[i-1]\n",
    "    # Rewrite values to the temporary array\n",
    "    for i in range(len(arr)-1, prev_to_last_idx, -1):\n",
    "        letter_idx = ord(arr[i][col_idx]) - a_code\n",
    "        temp[prev_to_last_idx + counts[letter_idx]] = arr[i]\n",
    "        counts[letter_idx] -= 1\n",
    "    # Rewrite sorted strings to the initial array\n",
    "    for i in range(prev_to_last_idx + 1, len(temp)):\n",
    "        arr[i] = temp[i]\n",
    "\n",
    "\n",
    "def longest_string_length(arr):\n",
    "    max_len = 0\n",
    "    for string in arr:\n",
    "        if len(string) > max_len:\n",
    "            max_len = len(string)\n",
    "    return max_len"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=== BEFORE: ===\n",
      "['pyktlcdkzjcusqyaclq',\n",
      " 'ujqmpochdfaihlkklc',\n",
      " 'biihzwgkjomdpmoln',\n",
      " '',\n",
      " 'armjytweokmrotgfg',\n",
      " 'efmoga',\n",
      " 'hwohp',\n",
      " 'nauzmwkboolwhjsnxgxapw',\n",
      " 'hszjqurnnspzruvpeoaixcgx',\n",
      " 'jakiyfgopbnjoaezkonfy',\n",
      " 'aavwhzjqjbbtp',\n",
      " 'oxwrblgghliplhc',\n",
      " 'imdkumdcdhtzmdfy',\n",
      " 'qdgtxvtwf',\n",
      " 'anhdozn',\n",
      " '',\n",
      " 'sgkzoqovwdxswatnpot',\n",
      " 'a',\n",
      " 'aaa',\n",
      " 'aaaaaa']\n",
      "\n",
      "\n",
      "=== AFTER: ===\n",
      "['',\n",
      " '',\n",
      " 'a',\n",
      " 'aaa',\n",
      " 'aaaaaa',\n",
      " 'aavwhzjqjbbtp',\n",
      " 'anhdozn',\n",
      " 'armjytweokmrotgfg',\n",
      " 'biihzwgkjomdpmoln',\n",
      " 'efmoga',\n",
      " 'hszjqurnnspzruvpeoaixcgx',\n",
      " 'hwohp',\n",
      " 'imdkumdcdhtzmdfy',\n",
      " 'jakiyfgopbnjoaezkonfy',\n",
      " 'nauzmwkboolwhjsnxgxapw',\n",
      " 'oxwrblgghliplhc',\n",
      " 'pyktlcdkzjcusqyaclq',\n",
      " 'qdgtxvtwf',\n",
      " 'sgkzoqovwdxswatnpot',\n",
      " 'ujqmpochdfaihlkklc']\n",
      "\n",
      "Is correct?: True\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "from string import ascii_lowercase as letters\n",
    "from pprint import pprint as pp\n",
    "\n",
    "rand_w = lambda length: ''.join(random.choice(letters) for _ in range(length))\n",
    "\n",
    "words = [rand_w(random.randint(0, 25)) for _ in range(random.randint(1, 40))] + ['a', 'aaa', 'aaaaaa']\n",
    "sorted_arr = sorted(words)\n",
    "print('=== BEFORE: ===')\n",
    "pp(words)\n",
    "print('\\n\\n=== AFTER: ===')\n",
    "radix_string_sort(words)\n",
    "pp(words)\n",
    "print('\\nIs correct?:', sorted_arr == words)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}